/*
 * Copyright (c) 1999, 2000, Robert Grimm.
 *    All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following
 * disclaimer in the documentation and/or other materials provided
 * with the distribution.
 *
 * 3. Neither name of Robert Grimm nor the names of his contributors
 * may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package one.eval;

import java.util.Collection;
import java.util.Iterator;
import java.util.AbstractList;
import java.util.List;
import java.util.ConcurrentModificationException;

import one.util.NegativeSizeException;

/**
 * Implementation of a vector. A vector is a modifiable list in the
 * sense of the Java collections framework. That is, its size is fixed
 * at creation time, but its elements can be changed. A vector also is
 * a Scheme vector.
 *
 * <p>A vector may optionally represent a literal, in which case the
 * vector itself and all its elements (recursively) are
 * unmodifiable. To be consistent with the Java collections framework,
 * all methods that modify such a vector throw a <code>
 * UnsupportedOperationException</code>. The {@link #isLiteral()}
 * method can be used to test whether a particular vector instance is
 * a literal. By default, all vectors are modifiable. Furthermore,
 * literal vectors can only be generated by other classes in this
 * package, in particular the Scheme reader.</p>
 *
 * <p>Note that operations on vectors are not synchronized.</p>
 *
 * @see      java.util.List
 * @see      java.util.AbstractList
 *
 * @author   &copy; Copyright 1998-2000 by Robert Grimm.
 *           Written by <a href="mailto:rgrimm@alum.mit.edu">Robert
 *           Grimm</a>.
 * @version  1.0
 */
public final class Vector extends AbstractList implements java.io.Serializable {

  /** An empty vector. */
  public static final Vector EMPTY = new Vector();

  /**
   * The elements of the vector.
   *
   * @serial The array of objects representing the vector
   *         elements. The length of the vector is the length of this
   *         array and each entry in the array is a vector
   *         element. <code>elements</code> must not be
   *         <code>null</code>.
   */
  private Object[] elements;

  /**
   * Flag to indicate whether this vector is to be treated as a
   * literal; that is, as an unmodifiable vector. An unmodifiable
   * vector must throw a <code>UnsupportedOperationException</code> on
   * all operations that would modify its state. By default, all newly
   * created vectors are modifiable.
   *
   * @serial  <code>true</code> iff the vector is to be treated as a
   *          literal.
   */
  private boolean literal = false;

  /** Create a new empty vector. */
  public Vector() {
    elements = new Object[0];
  }

  /**
   * Create a new vector that has the size of the specified collection
   * and contains all its elements in order.
   *
   * @param   c 
   *             The collection that defines the size of the vector and
   *             provides its initial elements.
   */
  public Vector(Collection c) {
    elements      = new Object[c.size()];

    Iterator iter = c.iterator();
    int      i    = 0;

    while (iter.hasNext()) {
      elements[i++] = iter.next();
    }
  }

  /**
   * Create a new vector that is as long as the specified array and
   * contains all its elements in the given order.
   *
   * @param   a
   *             The array that defines the size of the vector and
   *             provides its initial elements.
   */
  private Vector(Object[] a) {
    elements = new Object[a.length];
    System.arraycopy(a, 0, elements, 0, a.length);
  }

  /**
   * Create a new empty vector of the specified length.
   *
   * @param   length  The length of the vector.
   * @throws  NegativeSizeException
   *                  Signals that <code>length</code> is negative.
   */
  private Vector(int length) {
    if (length < 0) throw new NegativeSizeException();
    elements = new Object[length];
  }

  /**
   * Create a new vector of the specified length and fill it with
   * the specified element.
   *
   * @param   length
   *             The length of the vector.
   * @param   element
   *             The element to fill the vector with.
   * @throws  NegativeSizeException
   *             Signals that <code>length</code> is negative.
   */
  private Vector(int length, Object element) {
    this(length);
    fill(element);
  }
  
  /**
   * Create a new vector that is as long as the specified array and
   * contains all its elements in the given order. This method accepts
   * an <code>Object</code> argument instead of an
   * <code>Object[]</code> argument, so that it can also accept arrays
   * with a primitive component type.
   *
   * @param   a  The array that defines the size of the vector and
   *             provides its initial elements.
   * @return     A new vector that is as long as the specified array
   *             and contains all its elements in the given order.
   * @throws  IllegalArgumentException
   *             Signals that <code>a</code> is not an array.
   */
  public static Vector create(Object a) {
    if (! a.getClass().isArray()) {
      throw new IllegalArgumentException("Not an array");
    }

    int len = java.lang.reflect.Array.getLength(a);

    if (0 == len) {
      return EMPTY;
    } else {
      Vector v = new Vector(len);

      for (int i=0; i<len; i++) {
        v.elements[i] = java.lang.reflect.Array.get(a, i);
      }

      return v;
    }
  }

  /**
   * Create a new vector that is as long as the specified list and
   * contains all its elements in the given order.
   *
   * @param   p  The proper list starting at this pair that defines
   *             the size of the vector and provides its initial
   *             elements.
   * @return     A new vector that is as long as the specified list
   *             and contains all its elements in the given order, or
   *             the empty vector if <code>l</code> is the empty
   *             list {@link Pair#EMPTY_LIST '()}.
   * @throws  BadPairStructureException
   *             Signals that the pair does not start a proper
   *             list.
   */
  public static Vector create(Pair p) throws BadPairStructureException {
    if (Pair.EMPTY_LIST == p) return EMPTY;
    
    int    l = p.length();
    Vector v = new Vector(l);
    int    i = 0;
    do {
      v.elements[i++] = p.car;
      p = (Pair)p.cdr;
    } while (Pair.EMPTY_LIST != p);

    return v;
  }

  /**
   * Create a new vector of the specified length and fill it with
   * the specified element.
   *
   * @param   length
   *             The length of the vector.
   * @param   element
   *             The element to fill the vector with.
   * @return     A new vector of the specified length, filled with
   *             the specified element, or the empty vector if
   *             <code>length</code> is 0.
   * @throws  NegativeSizeException
   *             Signals that <code>length</code> is negative.
   */
  public static Vector create(int length, Object element) {
    if (0 == length) return EMPTY;
    return new Vector(length, element);
  }

  /**
   * Create a new vector that has the size of the specified collection
   * and contains all its elements in order.
   *
   * @param   c 
   *             The collection that defines the size of the vector and
   *             provides its initial elements.
   * @return     A new vector that has the size of the specified
   *             collection and contains all its elements in order.
   */
  public static Vector create(Collection c) {
    if (c.size() == 0) {
      return EMPTY;
    } else {
      return new Vector(c);
    }
  }

  /**
   * Clone this vector.
   *
   * @return  A newly allocated vector that is a copy of this vector,
   *          or this vector if this vector is the empty vector.
   */
  public Object clone() {
    if (0 == elements.length) {
      return this;
    } else {
      return new Vector(elements);
    }
  }
  
  /**
   * Return the length of this vector.
   *
   * @return The length of this vector.
   */
  public int size() {
    return elements.length;
  }

  /**
   * Return the vector element at the specified index.
   *
   * @param   index  The index of the vector element.
   * @return         The vector element at the specified index.
   * @throws  IndexOutOfBoundsException
   *                 Signals an invalid index.
   */
  public Object get(int index) {
    return elements[index];
  }

  /**
   * Replace the vector element at the specified index with the
   * specified element.
   *
   * @param   index    The index of the vector element.
   * @param   element  The new vector element at the specified index.
   * @return           The old vector element at the specified index.
   * @throws  IndexOutOfBoundsException
   *                   Signals an invalid index.
   * @throws  UnsupportedOperationException
   *                   Signals that this vector is a literal.
   */
  public Object set(int index, Object element) {
    if (literal) throw new UnsupportedOperationException();
    Object oldElement = elements[index];
    elements[index]   = element;
    return oldElement;
  }

  /**
   * Fill every element of this vector with the specified element.
   *
   * @param   o   The element to fill in.
   * @throws  UnsupportedOperationException
   *              Signals that this vector is a literal.
   */
  public void fill(Object o) {
    if (literal) throw new UnsupportedOperationException();
    java.util.Arrays.fill(elements, o);
  }

  /**
   * Test whether this vector is a literal. If this vector is a
   * literal, all its elements are literals and recursively, if any of
   * the elements are pairs or vectors, their elements are also
   * literals. Furthermore, none of these elements can be a string
   * buffer.
   *
   * @see     Pair#isLiteral()
   *
   * @return  <code>true</code> iff this vector is a literal.
   */
  public boolean isLiteral() {
    return literal;
  }

  /**
   * Turn this vector into a literal. Sets the literal flag for this
   * vector to <code>true</code> and <em>recursively</em> calls the
   * method of the same name for all vector elements that are either a
   * vector or a pair.
   *
   * @throws  UnsupportedOperationException
   *             Signals that a vector element is a string buffer
   *             instead of an unmodifiable Java string.
   */
  void turnIntoLiteral() {
    if (literal) {
      return;
    } else {
      // First, mark vector elements as literal.
      for (int i=0; i<elements.length; i++) {
        Object o = elements[i];
        if (o instanceof Vector) {
          ((Vector)o).turnIntoLiteral();
        } else if (o instanceof Pair) {
          ((Pair)o).turnIntoLiteral();
        } else if (o instanceof StringBuffer) {
          throw new UnsupportedOperationException();
        }
      }
      
      // Then, mark the vector itself as literal.
      literal = true;
    }
  }

  /**
   * Return the index of the first occurrence of the specified element
   * in this vector, or -1 if the vector does not contain this
   * element. Uses the <code>equals(Object)</code> method to
   * compare <code>o</code> to vector elements, unless <code>o</code>
   * is <code>null</code> in which case <code>==</code> is used.
   *
   * @param   o  The element to search for.
   * @return     The index of the first occurrence of the specified
   *             element, or -1 if the vector does not contain this
   *             element.
   */
  public int indexOf(Object o) {
    if (null == o) {
      for (int i=0; i<elements.length; i++) {
	if (null == elements[i]) {
	  return i;
	}
      }
    } else {
      for (int i=0; i<elements.length; i++) {
	if (o.equals(elements[i])) {
	  return i;
	}
      }
    }

    return -1;
  }

  /**
   * Return the index of the last occurrence of the specified element
   * in this vector, or -1 if the vector does not contain this
   * element. Uses the <code>equals(Object)</code> method to
   * compare <code>o</code> to vector elements, unless <code>o</code>
   * is <code>null</code> in which case <code>==</code> is used.
   *
   * @param   o  The element to search for.
   * @return     The index of the last occurrence of the specified
   *             element, or -1 if the vector does not contain this
   *             element.
   */
  public int lastIndexOf(Object o) {
    if (null == o) {
      for (int i=elements.length-1; i>=0; i--) {
	if (null == elements[i]) {
	  return i;
	}
      }
    } else {
      for (int i=elements.length-1; i>=0; i--) {
	if (o.equals(elements[i])) {
	  return i;
	}
      }
    }

    return -1;
  }

  /**
   * Return <code>true</code> iff this vector contains the specified
   * element. Uses the <code>equals(Object)</code> method to
   * compare <code>o</code> to vector elements, unless <code>o</code>
   * is <code>null</code> in which case <code>==</code> is used.
   *
   * @param   o  The element to search for.
   * @return     <code>true</code> iff this vector contains the
   *             specified element.
   */
  public boolean contains(Object o) {
    return (-1 != indexOf(o));
  }

  /**
   * Return a new array containing all elements of this vector in order.
   *
   * @return  A new array containing all elements of this vector.
   */
  public Object[] toArray() {
    Object[] a = new Object[elements.length];
    System.arraycopy(elements, 0, a, 0, elements.length);
    return a;
  }

  /**
   * Return a new pair-based list containing all elements of this
   * vector in order.
   *
   * @return  A new list containing all elements of this vector.
   */
  public Pair toList() {
    Pair result = Pair.EMPTY_LIST;

    for (int i=elements.length-1; i>=0; i--) {
      result = new Pair(elements[i], result);
    }

    return result;
  }

}
